package leetcode_200;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *Triangle_120 自顶向下的带备忘录的动态规划问题
 *describe:AC 94%
 *2018年5月22日 下午4:47:14
 */
public class Triangle_120 {

	public static void main(String[] args) {
		Triangle_120 test=new Triangle_120();
		List<Integer> l1=new ArrayList<Integer>();
		l1.add(2);
		List<Integer> l2=new ArrayList<Integer>();
		l2.add(3);
		l2.add(4);
		List<Integer> l3=new ArrayList<Integer>();
		l3.add(6);
		l3.add(5);
		l3.add(7);
		List<Integer> l4=new ArrayList<Integer>();
		l4.add(4);
		l4.add(1);
		l4.add(8);
		l4.add(3);
		
		List<List<Integer>> list=new ArrayList<List<Integer>>();
		list.add(l1);
		list.add(l2);
		list.add(l3);
		list.add(l4);
		System.out.println(test.minimumTotal(list));
	}
	/**
	 * describe:
	 * 2018年5月22日 下午4:45:37
	 * @param triangle  只能有两种选择
	 * @return
	 * int
	 */
	public int minimumTotal(List<List<Integer>> triangle) {
		if(triangle==null)
			return 0;
		if(triangle.size()==1)
		    return triangle.get(0).get(0);
		int index=triangle.size()-2;//从倒数第二层改变起
		List<Integer> lastList=triangle.get(triangle.size()-1);
		int dp[]=new int[lastList.size()];
		for(int i=0;i<dp.length;++i)
			dp[i]=lastList.get(i);
		
		while(index>=0) {
			List<Integer> nowList=triangle.get(index);
			for(int i=0;i<nowList.size();++i) {
				dp[i]=Math.min(dp[i], dp[i+1])+nowList.get(i);
			}
			--index;
		}
        return dp[0];
    }
	

}
